#pragma once
#include <iostream>
#include <cassert>
using namespace std;
namespace xzq
{
    template <class T>
    struct __list_node
    {
        __list_node<T> *_prev;
        __list_node<T> *_next;
        T _data;
        __list_node(const T &x = T())
            : _data(x), _prev(nullptr), _next(nullptr)
        {
        }
    };
    template <class T, class Ref, class Ptr>
    struct __list_iterator
    {
        typedef __list_node<T> Node;
        typedef __list_iterator<T, Ref, Ptr> Self;
        Node *_node;
        __list_iterator(Node *node)
            : _node(node)
        {
        }
        Ref operator*()
        {
            return _node->_data;
        }
        Ptr operator->()
        {
            return &_node->_data;
        }
        Self &operator++()
        {
            _node = _node->_next;
            return *this;
        }
        Self operator++(int)
        {
            Self tmp(*this);
            ++(*this);
            return tmp;
        }
        Self &operator--()
        {
            _node = _node->_prev;
            return *this;
        }
        Self operator--(int)
        {
            Self tmp(*this);
            --(*this);
            return tmp;
        }
        bool operator!=(const Self &it)
        {
            return _node != it._node;
        }
        bool operator==(const Self &it)
        {
            return _node == it._node;
        }
    };
    template <class T>
    class list
    {
        typedef __list_node<T> Node;

    public:
        typedef __list_iterator<T, T &, T *> iterator;
        typedef __list_iterator<T, const T &, const T *> const_iterator;
        iterator begin()
        {
            return iterator(_head->_next);
        }
        iterator end()
        {
            return iterator(_head);
        }
        const_iterator begin() const
        {
            return const_iterator(_head->_next);
        }
        const_iterator end() const
        {
            return const_iterator(_head);
        }
        list()
        {
            _head = new Node;
            _head->_next = _head;
            _head->_prev = _head;
        }
        ~list()
        {
            clear();
            delete _head;
            _head = nullptr;
        }
        void clear()
        {
            iterator it = begin();
            while (it != end())
            {
                erase(it++);
            }
        }
        list(const list<T> &lt)
        {
            _head = new Node;
            _head->_next = _head;
            _head->_prev = _head;
            for (auto e : lt)
            {
                push_back(e);
            }
        }
        list<T> &operator=(list<T> lt)
        {
            swap(_head, lt._head);
            return *this;
        }
        void push_back(const T &x)
        {
            insert(end(), x);
        }
        void pop_back()
        {
            erase(--end());
        }
        void push_front(const T &x)
        {
            insert(begin(), x);
        }
        void pop_front()
        {
            erase(begin());
        }
        void insert(iterator pos, const T &x)
        {
            Node *cur = pos._node;
            Node *prev = cur->_prev;
            Node *newnode = new Node(x);
            prev->_next = newnode;
            newnode->_prev = prev;
            newnode->_next = cur;
            cur->_prev = newnode;
        }
        void erase(iterator pos)
        {
            assert(pos != end());
            Node *cur = pos._node;
            Node *prev = cur->_prev;
            Node *next = cur->_next;
            delete cur;
            prev->_next = next;
            next->_prev = prev;
        }

    private:
        Node *_head;
    };
    void test()
    {
        list<int> l;
        l.push_back(1);
        l.push_back(2);
        l.push_back(3);
        l.push_back(4);
        l.pop_back();
        l.push_front(0);
        l.push_front(-1);
        l.pop_front();
        l.pop_front();
        list<int>::iterator it = l.begin();
        while (it != l.end())
        {
            cout << *it << " ";
            ++it;
        }
        cout << endl;
    }
    struct Date
    {
        int _year = 0;
        int _month = 1;
        int _day = 1;
    };
    void test1()
    {
        list<Date> l;
        l.push_back(Date());
        l.push_back(Date());
        l.push_back(Date());
        l.push_back(Date());
        list<Date>::iterator it = l.begin();
        while (it != l.end())
        {
            cout << it->_year << "-" << it->_month << "-" << it->_day << endl;
            cout << (*it)._year << "-" << (*it)._month << "-" << (*it)._day << endl;
            ++it;
        }
    }
    void print(const list<int> &lt)
    {
        auto it = lt.begin();
        while (it != lt.end())
        {
            cout << *it << " ";
            ++it;
        }
        cout << endl;
    }
    void test2()
    {
        list<int> l;
        l.push_back(1);
        l.push_back(2);
        l.push_back(3);
        l.push_back(4);
        print(l);
    }
}